package com.chenyi.algorithm.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找算法
 * 二分查找数组必须是有序的
 *
 * @author chenyi
 * @className BinarySearch
 * @date 2022/4/5 19:44
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 2, 3, 3, 3, 3, 5, 66, 111, 111, 111, 111, 222, 333, 333, 333};
        System.out.println(differenceSearch(arr, 0, arr.length - 1, 1));
    }

    /**
     * 二分查找
     *
     * @param arr       查找所需数组
     * @param left      左边下标
     * @param right     右边下标
     * @param findValue 需要查找的值
     * @return 查找结果的List
     */
    public static List<Integer> search(int[] arr, int left, int right, int findValue) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        int midValue = arr[mid];
        if (findValue < midValue) {
            return search(arr, left, mid - 1, findValue);
        } else if (findValue > midValue) {
            return search(arr, mid + 1, right, findValue);
        } else {
            List<Integer> nums = new ArrayList<>();

            // 往左边查找是否还有相同值
            int leftIndex = mid - 1;
            while (leftIndex >= 0 && arr[leftIndex] == findValue) {
                nums.add(leftIndex);
                leftIndex--;
            }
            // 将查找到的值添加到集合内
            nums.add(mid);

            // 往右边查找是否还有相同值
            int rightIndex = mid + 1;
            while (rightIndex < arr.length && arr[rightIndex] == findValue) {
                nums.add(rightIndex);
                rightIndex++;
            }
            return nums;
        }
    }

    /**
     * 差值查找
     * @param arr
     * @param left
     * @param right
     * @param findValue
     * @return
     */
    public static List<Integer> differenceSearch(int[] arr, int left, int right, int findValue) {
        if (left > right) {
            return null;
        }
        System.out.println("查询");
        int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
        int midValue = arr[mid];
        if (findValue < midValue) {
            return differenceSearch(arr, left, mid - 1, findValue);
        } else if (findValue > midValue) {
            return differenceSearch(arr, mid + 1, right, findValue);
        } else {
            List<Integer> nums = new ArrayList<>();

            // 往左边查找是否还有相同值
            int leftIndex = mid - 1;
            while (leftIndex >= 0 && arr[leftIndex] == findValue) {
                nums.add(leftIndex);
                leftIndex--;
            }
            // 将查找到的值添加到集合内
            nums.add(mid);

            // 往右边查找是否还有相同值
            int rightIndex = mid + 1;
            while (rightIndex < arr.length && arr[rightIndex] == findValue) {
                nums.add(rightIndex);
                rightIndex++;
            }
            return nums;
        }
    }


}
